To:        Dr. Eamon Barrett, NSF
From:      Dr. Douglas B. Lenat, Carnegie-Mellon University
Date:      July 7, 1978
Subject:   Annual Review of Research (NSF #7704440)
           July 1, 1977  --  June 30, 1978

The general  subject I'm studying is Discovery:   how are humans able
to beat what a priori seems an enormous search space, and continually
come up with viable, creative new syntheses?  In particular, how does
a  mathematician  know  which  concepts  to  define,  what  kinds  of
relationships  to hunt  for, how to  go about  proving conjectures he
suspects are  true, etc.?  The primary vehicle  for this research has
been a  theory (mathematicians are guided by  a very large collection
of  rules of  thumb)  and  a  computer  model embodying  it  (the  AM
program).   But AM's  limitation was that,  as new ever-more-specific
concepts  were defined  and developed, new  specific heurisitics were
not.  The focus of this past year's research has therefore been:  how
can we get our new  program (Eurisko) to discover new heuristic rules
of  thumb, rules which are  specific to the domains  that the program
itself discovers,  rules  which are  powerful enough  to  effectively
guide the program's search as it explores those new fields.

The hypothesis  we  made is  at once  bold,  risky, yet  the  obvious
first-order guess:  we can  walk around the space of heuristics using
pretty  much the same knowledge  we used to walk  around the space of
math concepts.  For instance, a  useful heuristic to AM said "Given a
new  function, pay special  attention to what it  maps extrema into".
Our  hypothesis says that this  can also be used  to guide the search
for  effective new  heuristics: "Given  a new  heuristic, pay special
atention to  what it  maps extrema  into".  In  the first  case,  the
extrema  were simply extreme  boundary examples of the  domain of the
function;  in the second  case, extrema refer to  extreme examples of
mathematical  concepts (e.g.,  extremely useful  ones, known frequent
counterexamples, etc.) The results to date are not yet conclusive; we
are still implementing.  Very soon we should know how far off we were
in our hypothesis about the nature of the space of heuristic rules.

Let me mention  how it is that we were  led to this hypothesis, since
it is not a part of the original proposal made last year.  For a long
period of time, we believed  that the key  lay in the codification of
a large number of  "meta-rules" -- informal pieces of knowledge about
how  to create  and manipulate heuristics.   But the  more we studied
such meta-rules, the more  elusive they became:  there is very little
which one can say about  heuristic rules that does not apply also to,
say,  mathematical operations.  E.g., "IF  the thing being considered
is very  costly to apply, that lowers its  overall worth rating"; "IF
the  thing sometimes produces  good results and  sometimes poor ones,
THEN try  to find a simple discriminator  that partitions the thing's
domain  into two classes,  most of the first  producing good results,
most of  the second producing inferior results;  and define and focus
on that thing restricted to the former subset of its old domain".

The basic  discovery, then,  was that  heuristics are  not so  unlike
mathematical  functions.    The   heuristics  relevant   to   walking
successfully around  the space of mathematical  functions might do an
adequate job  of walking  around  the space  of heuristics.   But  AM
already  had a  large collection of  just such  heuristics.  The task
that  was left was to  rewrite those heuristics in  a form that would
enable them to OPERATE UPON  EACH OTHER.  The solution was then quick
in appearing:   represent each  heuristic the  same way  in which  AM
represents each mathematical function: as a fulf-fledged concept with
facets (a frame with slots, a unit with aspects, a property list with
properties).   This   has   been  the   task   of  the   past   year,
re-representing all of AM's heuristics.

To date,  there is  one published  paper which  mentions this  year's
research:  "The Ubiquity of  Discovery".  This was the 1977 Computers
and Thought  Award  Lecture,  and was  reprinted  in THe  Journal  of
Artificial Intelligence,  Volume 9, Number 3,  in December, 1977.  It
was also an invited talk at -- and reprinted in the proceedings of --
the National Computer  Conference, Anaheim, June, 1978.  In addition,
this talk was an invited lecture at the Gordon Research Conference on
"Scientific Information  Problems  in Research",  this month  in  New
Hampshire.  Two  copies  are enclosed,  reprints  of the  AI  Journal
article.